

// 122.买卖股票的最佳时机II
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 动态规划
        // 两个状态:有股票和没股票
        int n = prices.size();
        vector<int> f(n) , g(n);         // f表示第i天有股票,g表示第i天没有股票
        f[0] = -prices[0];
        for(int i = 1; i < n ; i++)
        {
            f[i] = max(f[i - 1] , g[i - 1] - prices[i]);
            g[i] = max(g[i - 1] , f[i - 1] + prices[i]);
        }
        return g[n - 1];
    }
};